29/09/2017
\[ \]
Dynamic Queueing Networks: Simulation, Estimation and Prediction
What's a queue?
What's a queue?
Arrival time: \(a_j\), when customer \(j\) arrives
Service time: \(s_j\), how much time customer \(j\) needs with a server
Departure time: \(d_j\), when customer \(j\) has been served
Waiting time: \(w_j = d_j - a_j - s_j\), how long customer \(j\) waited to be served
Kendall's notation
\(f_{\delta} / f_s / K / C / n / R\)
\(f_{\delta}\): inter-arrival distribution
\(f_s\): service distribution
\(K\): number of servers
\(C\): capacity of system
\(n\): number of customers
\(R\): service discipline
Performance measures
system utilization: \(\rho = \frac{\mu}{\lambda}\)
The steady state probability of \(N\) customers in a \(M/M/K\) system is,
\[ \begin{align} P(0) &= \left[\frac{ (K \rho)^K}{K! (1 - \rho)} + 1 + \sum_{i=1}^{K-1} \frac{(K \rho)^i}{i!} \right]^{-1} \\ P(N) &= \begin{cases} P(0) \frac{(K \rho)^n }{N!} & \quad N \leq K\\ P(0) \frac{(K \rho)^n }{K! K^{N-K}} & \text{otherwise} \end{cases} , \label{eq:pn} \end{align} \]
Simulation
R package queuecomputer
It's fast
Computation time in milliseconds for varying numbers of passengers for each DES/queueing package.
Queueing Networks
Sutton, C., & Jordan, M. I. (2011). Bayesian inference for queueing networks and modeling of internet services. The Annals of Applied Statistics, 254-282.
International Airport
Queueing network model of an international airport terminal.
International Airport Data
Approach
Simulation is used to convert \(\mathbf{(a,s)}\) to departure times \(\mathbf{d}\). \(\mathbf{Z}\) in step 7 is a function of the \(\mathbf{(a,s)}, \mathbf{d}\) and \(\theta_C\). It reflects features such as average waiting time, average queue length and resource utilization.
Simulation
Simulation
library(AirportSimulator) suppressPackageStartupMessages(library(dplyr)) airport_simulate() %>% sample_frac()
## # A tibble: 15,602 x 49 ## FlightNo Passengers arrival chocks gate Aus Flight_lag distance ## <chr> <dbl> <dbl> <dbl> <dbl> <dbl> <dbl> <dbl> ## 1 STU374 204 844.81 849.81 7 0.5493974 10 50 ## 2 MMV426 202 475.15 480.15 11 0.1687726 12 100 ## 3 GFG548 188 437.41 442.41 8 0.7446436 9 50 ## 4 RDL588 207 509.19 514.19 8 0.3548210 7 50 ## 5 MGK352 205 873.68 878.68 4 0.2227345 10 25 ## 6 AJQ982 203 843.63 848.63 6 0.2964728 11 50 ## 7 QIH619 199 986.85 991.85 10 0.8941724 13 100 ## 8 MMV426 202 475.15 480.15 11 0.1687726 12 100 ## 9 OLY647 189 596.11 601.11 3 0.3986504 8 25 ## 10 HOC337 230 950.22 955.22 5 0.5917895 15 25 ## # ... with 15,592 more rows, and 41 more variables: walk_imm <dbl>, ## # walk_aerobridge <dbl>, walk_bh <dbl>, walk_quarantine <dbl>, ## # passenger_num <int>, service_aerobridge <dbl>, nationality <fctr>, ## # walk_AC <dbl>, route_prob <dbl>, route_imm <fctr>, service_rate <dbl>, ## # num_baggage <dbl>, route_prob_1_quarantine <dbl>, ## # route_prob_2_quarantine <dbl>, route_baggage <dbl>, service_imm <dbl>, ## # n_bags <int>, route_quarantine <chr>, rate_quarantine <dbl>, ## # service_quarantine <dbl>, service_bags <dbl>, server_imm <list>, ## # server_baggage <list>, server_quarantine <list>, arrive_AC <dbl>, ## # arrive_imm <dbl>, depart_imm <dbl>, arrival_bags <dbl>, ## # depart_bags <dbl>, arrive_bh <dbl>, depart_bh <dbl>, ## # arrive_quarantine <dbl>, depart_quarantine <dbl>, ## # route_imm_true <fctr>, dwell_AC <dbl>, wait_imm <dbl>, ## # dwell_imm <dbl>, wait_bh <dbl>, dwell_bh <dbl>, wait_q <dbl>, ## # dwell_q <dbl>
Estimation: Approximate Bayesian Computation
For many complex models \(f (y|\theta)\) is easy to sample from but difficult or impossible to evaluate. Intuitively we may think that the best way to estimate \(\theta\), based on observed data \(y\), is to take samples from \(f (y|\theta)\) with different values of \(\theta\) until \(x\) “looks like” \(y\).
Estimation: Maximum Mean Discrepancy
\[ \begin{align} \widehat{\text{MMD}}^2_b(X,Y|s) &= \frac{1}{m^2} \sum_{i,j = 1}^{m} k(x_i, x_j) \\ &\quad + \frac{1}{n^2} \sum_{i,j = 1}^{n} k(y_i, y_j) - \frac{2}{mn} \sum_{i,j = 1}^{m,n} k(x_i, y_j). \end{align} \]
Gretton, A., Borgwardt, K. M., Rasch, M., Schölkopf, B., & Smola, A. J. (2007). A kernel method for the two-sample-problem. In Advances in neural information processing systems (pp. 513-520).
Estimation
library(AirportSimulator) true_params <- c(0.2, 20, 1.1, 3.5, 0.8, 3) y <- airport_sim_1(true_params) x <- airport_sim_1(true_params) airport_MMD(y,x, threshold = 6)
## [1] 0.0243735
proposed_params <- c(0.2, 10, 0.5, 3.5, 0.8, 3) x <- airport_sim_1(proposed_params) airport_MMD(y,x, threshold = 6)
## [1] 0.04856347
Estimation
library(tidyr)
library(ggplot2)
data_frame(y = unlist(y), x = unlist(x), input_output = rep(c("input", "output"), each = 15602)) %>%
gather(key = "key", value = "time", y, x) %>%
ggplot(aes(x = time, col = input_output)) +
geom_density(adjust = 0.0001) +
facet_grid(key ~ .)
Estimation: Results
ABC posterior distributions.
Prediction
Distribution of average waiting time for passengers by flight. Resimulations with fixed parameters.
Prediction
Particle resampling of trajectories with data assimilation.
Thank you!
Anthony Ebert
Supervised by: Kerrie Mengersen, Paul Wu, Fabrizio Ruggeri
Email: ac.ebert@qut.edu.au
Github: AnthonyEbert
Twitter: @ace_ebert
Have a look at the R package queuecomputer
This work is supported by the Australian Research Council Centre of Excellence for Mathematical and Statistical Frontiers (ACEMS).